1. Field of the Invention
The present invention relates to an arithmetic circuit for performing all arithmetic operations in a finite field GF(2m).
2. Description of the Related Art
In recent years, finite fields have attracted much attention in computer and communication applications. For instance, forward error-correction codes have been widely used in digital communications. However, to design an error-correction circuit with both a high operation speed and a low circuit complexity, it is a necessity to have a multi-function arithmetic circuit. Therefore, there is a trend, when designing the multi-function arithmetic circuit, to reduce its complexity, shorten its calculating delay and increase its operation speed. As any skilled person knows, addition, multiplication, division, exponentiation and inverse multiplication are the most basic arithmetic operations in a finite field. To perform these arithmetic operations, several kinds of circuits have been proposed on different bases, such as dual basis, normal basis and standard basis. Usually, arithmetic operations on dual basis and normal basis need extra transformations, while arithmetic operations on standard basis need no more transformations. Consequently, the arithmetic circuit of the present invention applies the standard basis although some arithmetic operations are best implemented on dual basis or normal basis.
In a finite field GF(2m), an adder on standard basis is easily implemented by m XOR gates, and a parallel-in-parallel-out multiplier on standard basis is first implemented by B. A. Laws, Jr and C. K. Rushforth, see xe2x80x9cA cellular-array multiplier for finite fields GF(2m)xe2x80x9d in IEEE trans. Corput., vol.C-20, pp. 1573-1578, 1971. Further, to increase the operation speed of the cellular-array multiplier, another systolic-array product-sum multiplier is also disclosed by C. S. Yeh, Irving S. Reed and T. K. Truong, see xe2x80x9cSystolic multipliers for finite fields GF(2m)xe2x80x9d in IEEE trans. Comput., vol. C-33, pp.357-360, 1984. Comparing the operation speeds of these two multipliers, a multiplication needs 2m gate delays in the cellular-array multiplier and one celltime delays (about two gate delays) in the systolic-array product-sum multiplier. However, the circuit complexity of the systolic-array product-sum multiplier is far more complicated than that of the cellular-array multiplier. Also, the first input of the systolic-array product-sum multiplier has a latency (about 3 m celltime delays) before the first output is obtained, it is also improper to apply the systolic-array product-sum multiplier in a pipeline-structured circuit.
Theoretically, division in a finite field GF(2m) is implemented by a multiplication and an inverse multiplication, i.e., A/B=A*Bxe2x88x921, where A and B are elements in the finite field GF(2m). Inverse multiplication can be implemented by using a ROM table, applying Euclid""s rule or combining a series of multiplications. Nowadays, inverse multiplication is mostly implemented on normal basis because square can be implemented by a simple cyclic shifting. Similarly, exponentiation can be also implemented by using a ROM table or combining a series of multiplication. Following is a list of references:
[1] B. A. Laws, m Jr., and C. K. Rushforth, xe2x80x9cA cellular-array multipliers for finite fields GF(2m),xe2x80x9d IEEE Trans. Comput., vol. C-20, pp. 1573-1578, 1971.
[2] C. -S. Yeh, Irving S. Reeds and T. K. Truong, xe2x80x9cSystolic multipliers for finite fields GF(2m),xe2x80x9d IEEE Trans. Comput., vol. C-33, pp. 357-360, 1984.
[3] C. C. Wang, T. K. Truong, H. M. Shao, L. J. Dentsch, J. K. Omura, and I. S. Reed. xe2x80x9cVLSI architectures for computing multiplications and inverses in GF(2m).xe2x80x9d IEEE Trans. Comput., vol. C-34, pp. 709-716, 1985.
[4] H. Okano, and H. Imai xe2x80x9cA construction method of high-speed decoders using ROM""s for Bose-Chaudhuri-Hocquenghem and Reed-Solomon codes,xe2x80x9d IEEE Trans. Comput., vol. C-36, pp. 1165-1171, 1987.
[5] K. Araki, I. Fujita, and M. Morisue xe2x80x9cFast inverter over finite field based in Euclid""s algorithm,xe2x80x9d Trans. IEICE, vol. E-72, pp. 1230-1234, November 1989.
[6] P. A. Scott, S. J. Simmons, S. E. Tavares, and L. E. Peppard, xe2x80x9cArchitectures for exponentiation in GF(2m),xe2x80x9d IEEE J. Selected Areas in Commun., vol. 6, No. 3, pp. 578-586, April 1988.
[7] C. C. Wang, and D. Pei, xe2x80x9cA VLSI design for computing exponentiations in GF(2m) and its application to generate pseudorandom number sequences,xe2x80x9d IEEE Trans. Comput., vol. C-39, No.2 pp. 258-262, February 1990.
Wei has also proposed another cellular-array power-sum circuit in 1996, for performing AB2+C, where A, B and C are elements in the finite field GF(2m). Under this structure, other arithmetic circuits for performing exponentiation, inverse multiplication and division are also disclosed.
However, the mentioned arithmetic circuits are respectively designed for a specific arithmetic operation, which is never enough, for example, a forward error-correction decoder. In a finite field GF(2m), an arithmetic circuit with high-speed, low complexity, and versatile features is required. For example, the decoding process of Peterson""s direct solution method for decoding the 3-error-correcting Reed-Solomon code are:
(i) Calculate the syndrome value of the received word,
xe2x80x83Si=r(xcex1i)=r0+r1xc2x7(xcex1i)+r2xc2x7(xcex1i)2+ . . . rnxe2x88x921xc2x7(xcex1i)nxe2x88x921, where i=1, 2, 3, 4, 5, 6.
(ii) Determine error-location polynomial "sgr"(X) from the syndrome values. For example, if there are 3 errors in the received word, the error-location polynomial
"sgr"(X)=X3+"sgr"1X2+xcfx812X+"sgr"3, where
            σ      1        =                                        S            1                    ⁢                      xe2x80x83                    ⁢                      S            3                    ⁢                      xe2x80x83                    ⁢                      S            6                          +                              S            1                    ⁢                      xe2x80x83                    ⁢                      S            4                    ⁢                      xe2x80x83                    ⁢                      S            5                          +                              S            2            2                    ⁢                      xe2x80x83                    ⁢                      S            6                          +                              S            2                    ⁢                      xe2x80x83                    ⁢                      S            3                    ⁢                      xe2x80x83                    ⁢                      S            5                          +                              S            2                    ⁢                      xe2x80x83                    ⁢                      S            4            2                          +                              S            3            2                    ⁢                      xe2x80x83                    ⁢                      S            4                                                            S            1                    ⁢                      xe2x80x83                    ⁢                      S            3                    ⁢                      xe2x80x83                    ⁢                      S            5                          +                              S            1                    ⁢                      xe2x80x83                    ⁢                      S            4            2                          +                              S            2            2                    ⁢                      xe2x80x83                    ⁢                      S            5                          +                  S          3          3                                σ      2        =                                        S            1                    ⁢                      xe2x80x83                    ⁢                      S            4                    ⁢                      xe2x80x83                    ⁢                      S            6                          +                              S            1                    ⁢                      xe2x80x83                    ⁢                      S            5            2                          +                              S            2                    ⁢                      xe2x80x83                    ⁢                      S            3                    ⁢                      xe2x80x83                    ⁢                      S            6                          +                              S            2                    ⁢                      xe2x80x83                    ⁢                      S            4                    ⁢                      xe2x80x83                    ⁢                      S            5                          +                              S            3            2                    ⁢                      xe2x80x83                    ⁢                      S            5                          +                              S            3                    ⁢                      xe2x80x83                    ⁢                      S            4            2                                                            S            1                    ⁢                      xe2x80x83                    ⁢                      S            3                    ⁢                      xe2x80x83                    ⁢                      S            5                          +                              S            1                    ⁢                      xe2x80x83                    ⁢                      S            4            2                          +                              S            2            2                    ⁢                      xe2x80x83                    ⁢                      S            5                          +                  S          3          3                                σ      3        =                                        S            2                    ⁢                      xe2x80x83                    ⁢                      S            4                    ⁢                      xe2x80x83                    ⁢                      S            6                          +                              S            2                    ⁢                      xe2x80x83                    ⁢                      S            5            2                          +                              S            3            2                    ⁢                      xe2x80x83                    ⁢                      S            6                          +                  S          4          3                                                  S            1                    ⁢                      xe2x80x83                    ⁢                      S            3                    ⁢                      xe2x80x83                    ⁢                      S            5                          +                              S            1                    ⁢                      xe2x80x83                    ⁢                      S            4            2                          +                              S            2            2                    ⁢                      xe2x80x83                    ⁢                      S            5                          +                  S          3          3                    
(iii) Find the roots of the error-location polynomial "sgr"(X) to obtain error locators.
(iv) Calculate error values at each error locator. For example, if the error locators are X1, X2 and X3, the error values are respectively:             Y      1        =                                        S            1                    ⁢                      xe2x80x83                    ⁢                      X            2            2                    ⁢                      xe2x80x83                    ⁢                      X            3            3                          +                              S            2                    ⁢                      xe2x80x83                    ⁢                      X            2            3                    ⁢                      xe2x80x83                    ⁢                      X            3                          +                              S            3                    ⁢                      xe2x80x83                    ⁢                      X            2                    ⁢                      xe2x80x83                    ⁢                      X            3            3                          +                              S            1                    ⁢                      xe2x80x83                    ⁢                      X            2            3                    ⁢                      xe2x80x83                    ⁢                      X            3            2                          +                              S            2                    ⁢                      xe2x80x83                    ⁢                      X            2                    ⁢                      xe2x80x83                    ⁢                      X            3            3                          +                              S            3                    ⁢                      xe2x80x83                    ⁢                      X            2            2                    ⁢                      xe2x80x83                    ⁢                      X            3                                                            X            1                    ⁢                      xe2x80x83                    ⁢                      X            2            2                    ⁢                      xe2x80x83                    ⁢                      X            3            3                          +                              X            1            3                    ⁢                      xe2x80x83                    ⁢                      X            2                    ⁢                      xe2x80x83                    ⁢                      X            3            2                          +                              X            1            2                    ⁢                      xe2x80x83                    ⁢                      X            2            3                    ⁢                      xe2x80x83                    ⁢                      X            3                          +                              X            1            3                    ⁢                      xe2x80x83                    ⁢                      X            2            2                    ⁢                      xe2x80x83                    ⁢                      X            3                          +                  
                ⁢                  xe2x80x83                ⁢                              X            1                    ⁢                      xe2x80x83                    ⁢                      X            2            3                    ⁢                      xe2x80x83                    ⁢                      X            3            2                          +                              X            1            2                    ⁢                      xe2x80x83                    ⁢                      X            2                    ⁢                      xe2x80x83                    ⁢                      X            3            3                                          Y      2        =                                        S            1                    ⁢                      xe2x80x83                    ⁢                      X            3            2                    ⁢                      xe2x80x83                    ⁢                      X            1            3                          +                              S            2                    ⁢                      xe2x80x83                    ⁢                      X            1                    ⁢                      xe2x80x83                    ⁢                      X            3            3                          +                              S            3                    ⁢                      xe2x80x83                    ⁢                      X            1            2                    ⁢                      xe2x80x83                    ⁢                      X            3                          +                              S            1                    ⁢                      xe2x80x83                    ⁢                      X            1            2                    ⁢                      xe2x80x83                    ⁢                      X            3            3                          +                              S            2                    ⁢                      xe2x80x83                    ⁢                      X            1            3                    ⁢                      xe2x80x83                    ⁢                      X            3                          +                              S            3                    ⁢                      xe2x80x83                    ⁢                      X            1                    ⁢                      xe2x80x83                    ⁢                      X            3            2                                                            X            1                    ⁢                      xe2x80x83                    ⁢                      X            2            2                    ⁢                      xe2x80x83                    ⁢                      X            3            3                          +                              X            1            3                    ⁢                      xe2x80x83                    ⁢                      X            2                    ⁢                      xe2x80x83                    ⁢                      X            3            2                          +                              X            1            2                    ⁢                      xe2x80x83                    ⁢                      X            2            3                    ⁢                      xe2x80x83                    ⁢                      X            3                          +                              X            1            3                    ⁢                      xe2x80x83                    ⁢                      X            2            2                    ⁢                      xe2x80x83                    ⁢                      X            3                          +                  
                ⁢                  xe2x80x83                ⁢                              X            1                    ⁢                      xe2x80x83                    ⁢                      X            2            3                    ⁢                      xe2x80x83                    ⁢                      X            3            2                          +                              X            1            2                    ⁢                      xe2x80x83                    ⁢                      X            2                    ⁢                      xe2x80x83                    ⁢                      X            3            3                                          Y      3        =                                        S            1                    ⁢                      xe2x80x83                    ⁢                      X            1            2                    ⁢                      xe2x80x83                    ⁢                      X            2            3                          +                              S            2                    ⁢                      xe2x80x83                    ⁢                      X            1            3                    ⁢                      xe2x80x83                    ⁢                      X            2                          +                              S            3                    ⁢                      xe2x80x83                    ⁢                      X            1                    ⁢                      xe2x80x83                    ⁢                      X            2            2                          +                              S            1                    ⁢                      xe2x80x83                    ⁢                      X            1            3                    ⁢                      xe2x80x83                    ⁢                      X            2            2                          +                              S            2                    ⁢                      xe2x80x83                    ⁢                      X            1                    ⁢                      xe2x80x83                    ⁢                      X            2            3                          +                              S            3                    ⁢                      xe2x80x83                    ⁢                      X            1            2                    ⁢                      xe2x80x83                    ⁢                      X            2                                                            X            1                    ⁢                      xe2x80x83                    ⁢                      X            2            2                    ⁢                      xe2x80x83                    ⁢                      X            3            3                          +                              X            1            3                    ⁢                      xe2x80x83                    ⁢                      X            2                    ⁢                      xe2x80x83                    ⁢                      X            3            2                          +                              X            1            2                    ⁢                      xe2x80x83                    ⁢                      X            2            3                    ⁢                      xe2x80x83                    ⁢                      X            3                          +                              X            1            3                    ⁢                      xe2x80x83                    ⁢                      X            2            2                    ⁢                      xe2x80x83                    ⁢                      X            3                          +                  
                ⁢                  xe2x80x83                ⁢                              X            1                    ⁢                      xe2x80x83                    ⁢                      X            2            3                    ⁢                      xe2x80x83                    ⁢                      X            3            2                          +                              X            1            2                    ⁢                      xe2x80x83                    ⁢                      X            2                    ⁢                      xe2x80x83                    ⁢                      X            3            3                              
Thus, the received word can be corrected with reference to the calculated error value, and the decoding procedure is accomplished, (see xe2x80x9cError-Control Techniques for Digital Communicationxe2x80x9d by A. M. Michelson and A. H. Levesque in 1985 and xe2x80x9cError Control Codingxe2x80x9d by S. Lin and D. J. Costellor in 1983).
To solve the above mentioned problems, it is an object of the present invention to provide an arithmetic circuit which can perform all arithmetic operations in the finite field, including addition, multiplication, division, exponentiation and inverse multiplication.
It is an object of the present invention to provide an arithmetic circuit, which can perform all basic arithmetic operations in a finite field GF(2m), including addition, multiplication, division, exponentiation and inverse multiplication. The arithmetic circuit of the present invention is structured with a low circuit complexity, so that an error-correction decoder applying this arithmetic circuit can be greatly simplified.